void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];

		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}

			a[end + 1] = tmp;
		}
	}
}



void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];

			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}

				a[end + gap] = tmp;
			}
		}
	}
}


#include <stdio.h>
#include <stdlib.h>

int TreeSize(struct TreeNode* root)
{
	return NULL == root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void _preorderTraversal(struct TreeNode* root, int* a, int* pi)
{
	if (NULL == root)
	{
		return;
	}

	a[(*pi)++] = root->val;
	_preorderTraversal(root->left, a, pi);
	_preorderTraversal(root->right, a, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
	*returnSize = TreeSize(root);
	int* a = (int*)malloc(sizeof(int) * (*returnSize));
	int i = 0;
	_preorderTraversal(root, a, &i);
	return a;
}



struct TreeNode* invertTree(struct TreeNode* root)
{
	if (NULL == root)
	{
		return NULL;
	}

	struct TreeNode* tmp = root->left;
	root->left = root->right;
	root->right = tmp;

	invertTree(root->left);
	invertTree(root->right);

	return root;
}


bool IsSameTree(struct TreeNode* root1, struct TreeNode* root2)
{
	if (NULL == root1 && NULL == root2)
	{
		return true;
	}

	if (NULL == root1 || NULL == root2)
	{
		return false;
	}

	if (root1->val != root2->val)
	{
		return false;
	}

	return IsSameTree(root1->left, root2->left) && IsSameTree(root1->right, root2->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
	if (NULL == root)
	{
		return false;
	}

	if (root->val == subRoot->val)
	{
		bool ret = IsSameTree(root, subRoot);

		if (ret)
		{
			return ret;
		}
	}

	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}



#include <stdio.h>

typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	char val;
}BTNode;

BTNode* CreateTree(char* a, int* pi)
{
	if ('#' == a[*pi])
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->val = a[(*pi)++];
	root->left = CreateTree(a, pi);
	root->right = CreateTree(a, pi);

	return root;
}

void InOrder(BTNode* root)
{
	if (NULL == root)
	{
		return;
	}

	InOrder(root->left);
	printf("%c ", root->val);
	InOrder(root->right);
}

int main()
{
	char a[100];
	scanf("%s", a);
	int i = 0;
	BTNode* root = CreateTree(a, &i);
	InOrder(root);

	return 0;
}